package com.demo.algorithms.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 归并排序：时间复杂度为O(N*logN)
 * 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
 * 若将两个有序表合并成一个有序表，称为二路归并。
 * <p>
 * 归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。
 * 该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
 * <p>
 * 1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
 * 2.设定两个指针，最初位置分别为两个已经排序序列的起始位置；
 * 3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
 * 4.重复步骤 3 直到某一指针达到序列尾；
 * 5.将另一序列剩下的所有元素直接复制到合并序列尾。
 *
 * @author: 蔡奇峰
 * @date: 2020/7/28 下午9:45
 */
public class MergeSort {

    public static void main(String[] args) {
//        int[] arr = {6, 2, 5, 2, 8, 66, 22, 17, 18, 1, 88, 98, 168, 178};

        int[] arr = new int[67780];
        for (int i = 0; i < 67780; i++) {

            arr[i] = new Random().nextInt(18060);
        }
        System.out.println("数组排序前：" + Arrays.toString(arr));

        long timeMillis = System.currentTimeMillis();
        int[] result = sort(arr, 0, arr.length - 1);
        long timeMilli = System.currentTimeMillis();

        System.out.println("归并排序耗时：" + (timeMilli - timeMillis));
        System.out.println("数组排序后：" + Arrays.toString(result));

    }


    /**
     * 归并排序
     *
     * @param arr   需要排序的数组（从小到大）
     * @param start 数组起始下标
     * @param end   数组末尾下标
     * @return
     */
    public static int[] sort(int[] arr, int start, int end) {
        // 如果start和end相等则说明数组只有一个元素,退出递归的条件
        if (start == end) {
            return new int[]{arr[start]};
        }
        int middle = start + (end - start) / 2;
        // 左有序数组
        int[] left = sort(arr, start, middle);
        // 右有序数组
        int[] right = sort(arr, middle + 1, end);
        // 1.申请空间,新有序数组
        int[] newArr = new int[left.length + right.length];

        // 遍历数组并比较
        int n = 0, l = 0, r = 0;
        while (l < left.length && r < right.length) {
            // 比较并交换
            // 使用三目运算符
            newArr[n++] = left[l] < right[r] ? left[l++] : right[r++];
            // 普通的if else
            /*if (left[l] < right[r]){
                newArr[n++] = left[l];
                l++;
            }else {
                r ++;
            }*/

        }

        // 将剩下的左数组复制到新数组
        while (l < left.length) {
            newArr[n++] = left[l++];
        }

        // 将剩下的右数组复制到新数组
        while (r < right.length) {
            newArr[n++] = right[r++];
        }

        return newArr;
    }

}
